前言
之前对0-1背包就理解的不是很好，并且时间长了会忘的。
这次又重新复习一下，理解了好几个以前没理解的点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190题目
现有n件物品，每一件的重量是w[i],价值是v[i]。用一个容量为c的背包来装这些东西，
问如何选择物品才能使装的物品价值最大？（每件物品只能放一次）
思路
我们会想该放哪i件物品到容量c的背包中呢。
我们可以用dp(i,j)来表示前i件物品放入容量j的背包中地最大价值。针对第i件物品,我们要先考虑
背包容量是否大于物品容量：
如果小于：那就不放，dp(i,j)=dp(i-1,j)。
如果大于：再考虑是否要放入：
这个时候要从放或不放第i件物品中选择一个价值更大的：dp(i,j)=max{ dp(i-1,j) , dp(i-1,j-w(i))+v(i) }
另外，起始值dp[0][j]=dp[i][0]=0;
算法实现
首先用二维数组dp(i,j)变成dp[i][j]。
dp[i][j]有好多的状态啊，能有n*c个，这么多状态按照怎样的顺序来计算呢，所以需要找出前后关系来。
可以看出每一个状态都是跟上一个状态有关的，要求装i件时的价值需要知道装i-1件时候的最大价值，所以得有个外层循环i:0.....n
每一次都是只需要dp[i-1][1,2,3.....]中的值，所以对于j来说呢好像顺序无所谓了。
由此可以写出代码：
-----------------------------------------
using namespace std;
int dp[1005][1005];
int main(){
int T;
int M;
int maxx=0;
int t[1111];
int p[1111];
while(scanf("%d %d",&T,&M)!=EOF){
maxx=0;
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
for(int i=1;i<=M;i++){
scanf("%d %d",&t[i],&p[i]);
}
for(int i=1;i<=M;i++){
for(int j=1;j<=T;j++){ //因为j的顺序无所谓，for(int j=T;j>=1;j--)也可以
if(j>=t[i]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+p[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
printf("%d\n",dp[M][T]);
}
return 0;
}
-----------------------------------------
打印状态矩阵dp
样例：
10 5//容量 物品数量
2 6//第一件物品的 重量 价值
2 3
6 5
5 4
4 6
| 1 2 3 4 5 6 7 8 9 10
--+----------------------------------------------------
1 | 0 6 6 6 6 6 6 6 6 6
2 | 0 6 6 9 9 9 9 9 9 9
3 | 0 6 6 9 9 9 9 11 11 14
4 | 0 6 6 9 9 9 10 11 13 14
5 | 0 6 6 9 9 12 12 15 15 15
照着这个矩阵手动推算一遍会加深理解,可以按照i：0...n,j:0...c的顺序。
也可以按照i:0...n,j:c...0的顺序，(按照这种顺序推算，也许就可以发现后面讲的优化为一维数组的方法。)
路径记录
之前不是说每一件物品都有放或不放两种选择吗，想要记录路径就得在放的时候给标记一下。
关键代码如下：
----------------------
for(int i=1;i<=M;i++){
//for(int j=1;j<=T;j++){
for(int j=T;j>=1;j--){
if(j>=t[i]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+p[i]);
if(dp[i-1][j]<(dp[i-1][j-t[i]]+p[i])){//记录路径
path[i][j]=1;//记录路径
}//记录路径
}else{
dp[i][j]=dp[i-1][j];
}
}
}
----------------------
路径输出
下面是路径矩阵
0 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 1 1 1 1
我们需要从这个矩阵中找出选取的哪些物品，应当从最后一个状态往前找。
比如说有多条从一个点出发的路径，你想要找到达顶点a的路径，肯定是从a往前这一条路找过去就行了。
代码如下：
----------------------
int i=M,j=T;//物品数量 背包容量
while(i&&j){
if(path[i][j]==1){
printf("%d ",i);
j-=t[i];
}
i--;
}
---------------------
一维数组优化
还是以上面的数据为例：
| 1 2 3 4 5 6 7 8 9 10
--+----------------------------------------------------
1 | 0 6 6 6 6 6 6 6 6 6
2 | 0 6 6 9 9 9 9 9 9 9
3 | 0 6 6 9 9 9 9 11 11 14
4 | 0 6 6 9 9 9 10 11 13 14
5 | 0 6 6 9 9 12 12 15 15 15
观察这个矩阵，会发现某一个状态dp[i][j]跟两个元素有关，一个是它的正上方的元素，另一个是它的上一行的左边的某一个元素
上面不是说过内层循环j可以从T....0吗，也就是j的顺序是无所谓的。
那么我们可以用这种顺序来观察上面的矩阵，
当我们计算dp[2][10]的时候，dp[2][10]=max{dp[1][10],dp[1][10-2]+3},结果是9，这时候可以不用把9写在第二行里，
我们可以把它写在dp[1][10]的位置(其实这个位置原来的数据已经没用了，因为后面任何一个状态都不会再用刀这个值了)
同样一次类推，把数据都写在第一行。
就这样每一行从后往前计算，只用一个一维数组就够了。
(如果每一行从前往后计算是不可以用一维数组的，比如在计算完dp[2][4]的时候，如果覆盖掉dp[1][4]的值，
但是再计算后面的dp[2][*]的时候是会用到那个值的)
最终代码：
------------------------------------------------
#include<cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int dp[1005];
int path[1005][1005];
int main(){
int T;
int M;
int t[1111];
int p[1111];
while(scanf("%d %d",&T,&M)!=EOF){
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
for(int i=1;i<=M;i++){
scanf("%d %d",&t[i],&p[i]);
}
for(int i=1;i<=M;i++){
for(int j=T;j>=1;j--){
if(j>=t[i]&&dp[j]<dp[j-t[i]]+p[i]){
path[i][j]=1;
dp[j]=dp[j-t[i]]+p[i];
}
}
}
printf("%d\n",dp[T]);
for(int i=1;i<=M;i++){
for(int j=1;j<=T;j++){
printf("%d ",path[i][j]);
}
printf("\n");
}
int i=M,j=T;
while(i&&j){
if(path[i][j]==1){
printf("%d ",i);
j-=t[i];
}
i--;
}
}
return 0;
}
/*
10 5
2 6
2 3
6 5
5 4
4 6
*/
---------------------------------------------------------
欢迎与我分享你的经验和见解。
转载请注明出处：http://taowusheng.cn/